package com.lw.leetcode.dp.b;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * 面试题 08.02. 迷路的机器人
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/13 14:53
 */
public class PathWithObstacles {

    public static void main(String[] args) {
        PathWithObstacles test = new PathWithObstacles();

        // [[0,0],[0,1],[0,2],[1,2],[2,2]]
        int[][] arr = {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};

        List<List<Integer>> lists = test.pathWithObstacles(arr);
        System.out.println(lists);
    }

    public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        if (m == 0 || obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][obstacleGrid[0].length - 1] == 1) {
            return Collections.emptyList();
        }
        int n = obstacleGrid[0].length;
        obstacleGrid[0][0] = 2;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    continue;
                }
                if (i != 0 && obstacleGrid[i - 1][j] != 1 && obstacleGrid[i - 1][j] != 0) {
                    obstacleGrid[i][j] = 2;
                } else if (j != 0 && obstacleGrid[i][j - 1] != 1 && obstacleGrid[i][j - 1] != 0) {
                    obstacleGrid[i][j] = 3;
                }
            }
        }
        int v = obstacleGrid[m - 1][n - 1];
        if (v == 0) {
            return Collections.emptyList();
        }
        List<List<Integer>> list = new ArrayList<>(m + n - 1);
        int i = m - 1;
        int j = n - 1;
        while (i > 0 || j > 0) {
            list.add(Arrays.asList(i, j));
            if (obstacleGrid[i][j] == 2) {
                i--;
            } else {
                j--;
            }
        }
        list.add(Arrays.asList(i, j));
        Collections.reverse(list);
        return list;
    }

}
